Data storage applications have conventionally employed distributed hash tables (DHTs) for storing data. As is known, a DHT includes a ring of computing nodes in which each node has a pointer to a successor node and in which nodes are identified for data storage using a hash key. In a conventional scenario, a “keyspace” (i.e., range of possible values) of a hash key is divided among the nodes of a DHT ring, with each successor node (except the first) covering the next highest range of keyspace values. To store data in a DHT ring, a hash function is applied to the data or to some identifier associated with the data to produce a hash key. The hash key is then applied to the DHT ring and passed from one node to the next until a matching slot is identified. The matching “slot” is the node having the keyspace range that encompasses the hash key. The data are then stored in the matching node. Metadata are generally created to maintain the location of the stored data within the DHT ring. To retrieve stored data from a DHT ring, the metadata are accessed, the node on which the data are stored is identified, and the data are read from the identified node.
Prior examples of DHTs used for data placement include the Chord system developed at MIT and the Dynamo storage system developed by Amazon.com.